package com.pan.alg.leecode;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;

/**
 * NC65 斐波那契数列
 *
 * 大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项
 * @author by panstark
 * @description
 * @notice
 * @date 2022/1/17
 */
@Slf4j
public class Fibonacci {

    int[] memo;
   public int findN(int n){
       memo= new int[n+1];
       int i = calcalN(n);
       return i;
   }


    private int calcalN(int n) {
       if(n==0){
           return 0;
       }
       if(n==1||n==2){
           return 1;
       }
       if(memo[n]!=0){
           return memo[n];
       }
       memo[n] = calcalN(n-1)+calcalN(n-2);

       return memo[n];
    }

    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        int n = fibonacci.findN(2);
        System.out.println(n);

    }


}
